{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest BST Subtree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestBSTSubtree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大 BST 子树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，并返回该子树的大小。其中，最大指的是子树节点数最多的。</p>\n",
    "\n",
    "<p><strong>二叉搜索树（BST）</strong>中的所有节点都具备以下属性：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>\n",
    "\t<p>左子树的值小于其父（根）节点的值。</p>\n",
    "\t</li>\n",
    "\t<li>\n",
    "\t<p>右子树的值大于其父（根）节点的值。</p>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意：</strong>子树必须包含其所有后代。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/17/tmp.jpg\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [10,5,15,1,8,null,7]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>本例中最大的 BST 子树是高亮显示的子树。返回值是子树的大小，即 3 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树上节点数目的范围是 <code>[0, 10<sup>4</sup>]</code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= Node.val &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶:</strong>&nbsp; 你能想出 O(n) 时间复杂度的解法吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-bst-subtree](https://leetcode.cn/problems/largest-bst-subtree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-bst-subtree](https://leetcode.cn/problems/largest-bst-subtree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,5,15,1,8,null,7]', '[4,2,7,2,3,5,null,2,null,null,null,null,null,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans=0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return float(\"inf\"),float(\"-inf\"),0\n",
    "            lmin,lmax,lv=dfs(root.left)\n",
    "            rmin,rmax,rv=dfs(root.right)\n",
    "            if lmax<root.val<rmin:\n",
    "                print(lv+rv+1)\n",
    "                self.ans=max(self.ans,lv+rv+1)\n",
    "                return min(root.val,lmin),max(root.val,rmax),lv+rv+1 ### 始终保存的是最大的值\n",
    "            return float('-inf'),float('inf'),max(lv,rv) ### 这就是不可能再次是bst了 \n",
    "            ### 最后一行就是可以传递的原因，直接dfs(root) 的原因\n",
    "        dfs(root)\n",
    "        #return dfs(root)[2]\n",
    "        return self.ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "\n",
    "# class TreeNode:\n",
    "\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "\n",
    "#         self.val = val\n",
    "\n",
    "#         self.left = left\n",
    "\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        _min, _max =float('-inf'), float('inf')\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return _max,_min,0\n",
    "            lmin,lmax,lcnt = dfs(root.left)\n",
    "            rmin,rmax,rcnt = dfs(root.right)\n",
    "            if lmax<root.val and root.val<rmin:\n",
    "                nonlocal ans\n",
    "                #print(root.val)\n",
    "                ans = max(ans,lcnt+rcnt+1)\n",
    "                #这里min，max针对左右子树为空的情况\n",
    "                return min(root.val,lmin),max(root.val,rmax),lcnt+rcnt+1\n",
    "            return _min,_max,0\n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return float(\"inf\"),float(\"-inf\"),0\n",
    "            lmin,lmax,lv=dfs(root.left)\n",
    "            rmin,rmax,rv=dfs(root.right)\n",
    "            if lmax<root.val<rmin:\n",
    "                return min(root.val,lmin),max(root.val,rmax),lv+rv+1 ### 始终保存的是最大的值\n",
    "            return float('-inf'),float('inf'),max(lv,rv) ### 这就是不可能再次是bst了\n",
    "        return dfs(root)[2]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(x):\n",
    "            if x is None:\n",
    "                return inf,-inf,0\n",
    "            l_Min,l_Max,lv=dfs(x.left)\n",
    "            r_Min,r_Max,rv=dfs(x.right)\n",
    "            if l_Max<x.val<r_Min:\n",
    "                return min(l_Min,x.val),max(r_Max,x.val),lv+rv+1\n",
    "            return -inf,inf,max(lv,rv)\n",
    "        return dfs(root)[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root:TreeNode):\n",
    "        if root == None:\n",
    "            return float('inf'), float('-inf'), 0\n",
    "\n",
    "        l_min, l_max, l_cnt = self.dfs(root.left)\n",
    "        r_min, r_max, r_cnt = self.dfs(root.right)\n",
    "\n",
    "        if l_max < root.val < r_min:\n",
    "            return min(l_min, root.val), max(root.val, r_max), l_cnt + r_cnt + 1\n",
    "        else:\n",
    "            return float('-inf'), float('inf'), max(l_cnt, r_cnt)\n",
    "\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.dfs(root)[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root):\n",
    "            nonlocal ans \n",
    "            if root is None:\n",
    "                return 0, float('-inf'), float('inf')\n",
    "            du, mx, mn = 0, root.val, root.val\n",
    "            du1, mx1, mn1 = dfs(root.left) \n",
    "            du2, mx2, mn2 = dfs(root.right)\n",
    "            if mx1 < root.val < mn2 and du1 >= 0 and du2 >= 0:\n",
    "                du = du1 + du2 + 1 \n",
    "            else:\n",
    "                du = float('-inf')  \n",
    "            mx = max(mx, mx2)\n",
    "            mn = min(mn, mn1) \n",
    "            ans = max(ans, du) \n",
    "            return du, mx, mn \n",
    "        dfs(root) \n",
    "        return ans if ans > float('-inf') else 0 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def helper(node, low, up):\n",
    "            if not node:\n",
    "                return 1\n",
    "            cur_val = node.val\n",
    "            if (cur_val <= low or cur_val >= up):\n",
    "                return 0\n",
    "            return helper(node.left,low,cur_val) and helper(node.right,cur_val,up)\n",
    "        \n",
    "        def cnt(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return cnt(node.left) + cnt(node.right) + 1\n",
    "        \n",
    "        if not root: return 0\n",
    "        if (helper(root, float('-inf'), float('inf'))):\n",
    "            return cnt(root)\n",
    "        return max(self.largestBSTSubtree(root.left), self.largestBSTSubtree(root.right))\n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.dfs(root)[2]\n",
    "    \n",
    "    def dfs(self, node):\n",
    "        if node == None:\n",
    "            return float('inf'), float('-inf'), 0\n",
    "            \n",
    "        L_min, L_max, L_cnt = self.dfs(node.left)\n",
    "        R_min, R_max, R_cnt = self.dfs(node.right)\n",
    "\n",
    "        # BST树成立\n",
    "        if L_max < node.val < R_min:\n",
    "            return min(L_min, node.val), max(R_max, node.val), L_cnt + R_cnt + 1\n",
    "        # BST树不成立\n",
    "        else:\n",
    "            return float('-inf'), float('inf'), max(L_cnt, R_cnt)\n",
    "\n",
    "\n",
    "\n",
    "# # Definition for a binary tree node.\n",
    "# # class TreeNode:\n",
    "# #     def __init__(self, val=0, left=None, right=None):\n",
    "# #         self.val = val\n",
    "# #         self.left = left\n",
    "# #         self.right = right\n",
    "# class Solution:\n",
    "#     def largestBSTSubtree(self, root: TreeNode) -> int:\n",
    "#         return self.dfs(root)[2]\n",
    "\n",
    "#     def dfs(self, root: TreeNode):\n",
    "#         if root == None:\n",
    "#             return float('inf'),  float('-inf'),  0   #对所有的父节点。它都是配合的，ok的\n",
    "\n",
    "#         L_min, L_max, L_cnt = self.dfs(root.left)\n",
    "#         R_min, R_max, R_cnt = self.dfs(root.right)\n",
    "\n",
    "#         if L_max < root.val < R_min:                    #若能构成BST\n",
    "#             return min(L_min, root.val),  max(root.val, R_max),  L_cnt + R_cnt + 1\n",
    "\n",
    "#         else:                                           #不能构成BST\n",
    "#             return float('-inf'),  float('inf'),  max(L_cnt, R_cnt) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def find(root: Optional[TreeNode]):\n",
    "            nonlocal res\n",
    "            if not root: return [10**5,-10**5,0],True\n",
    "            l,lb = find(root.left)\n",
    "            r,rb = find(root.right)\n",
    "            if not lb or not rb: return [0],False\n",
    "            if l[1]<root.val and r[0]>root.val:\n",
    "                num = l[2]+r[2]+1\n",
    "                res = max(res,num)\n",
    "                min_v = l[0] if root.left else root.val\n",
    "                max_v = r[1] if root.right else root.val\n",
    "                return [min_v,max_v,num],True\n",
    "            else:\n",
    "                return [0],False\n",
    "\n",
    "        find(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        m = 1\n",
    "        def dfs(root):\n",
    "            nonlocal m\n",
    "            if not root:\n",
    "                return 0,10001,-10001\n",
    "            if (not root.left) and (not root.right):\n",
    "                return 1,root.val,root.val\n",
    "            l,lmi,lma = dfs(root.left)\n",
    "            r,rmi,rma = dfs(root.right)\n",
    "            if l==-1 or r==-1:\n",
    "                return -1,10001,-10001\n",
    "            if l==0 and r==0:\n",
    "                cur = 1\n",
    "            elif l==0:\n",
    "                if r==-1 or root.val>=rmi:\n",
    "                    cur = -1\n",
    "                else:\n",
    "                    cur = r+1\n",
    "            elif r==0:\n",
    "                if l==-1 or root.val<=lma:\n",
    "                    cur = -1\n",
    "                else:\n",
    "                    cur = l+1\n",
    "            else:\n",
    "                if l==-1 or r==-1:\n",
    "                    cur = -1\n",
    "                elif lma<root.val<rmi:\n",
    "                    cur = l+r+1\n",
    "                else:\n",
    "                    cur = -1\n",
    "            m = max(cur,m)\n",
    "            return cur,min(root.val,lmi),max(root.val,rma)\n",
    "        _ = dfs(root)\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def valid(self, root, left_bound = float(\"-inf\"), righ_bound = float(\"inf\")):\n",
    "        \"\"\"\n",
    "        验证当前节点的子树是否为二叉搜索树\n",
    "        \"\"\"\n",
    "        if root == None: # 空节点为二叉搜索树\n",
    "            return 1\n",
    "        if root.val <= left_bound or root.val >= righ_bound:\n",
    "            return 0\n",
    "        return self.valid(root.left, left_bound, root.val) and self.valid(root.right, root.val, righ_bound) \n",
    "\n",
    "\n",
    "    def count(self, root):\n",
    "        if root == None:\n",
    "            return 0\n",
    "        return self.count(root.left) + self.count(root.right) + 1\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        if self.valid(root):\n",
    "            return self.count(root)\n",
    "        return max(self.largestBSTSubtree(root.left), self.largestBSTSubtree(root.right))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        def isBST(_root):\n",
    "            nonlocal res\n",
    "            assert _root is not None\n",
    "            if _root.left is None and _root.right is None:\n",
    "                res = max(res, 1)\n",
    "                return (True, _root.val, _root.val, 1)\n",
    "\n",
    "            cur_size = 1\n",
    "            cur_min_val = cur_max_val =  _root.val\n",
    "\n",
    "            flg = True\n",
    "            if _root.right:\n",
    "                flg_r, min_val, max_val, size = isBST(_root.right)\n",
    "                flg = flg and flg_r and (_root.val < min_val)\n",
    "                cur_size += size\n",
    "                cur_max_val = max(cur_max_val, max_val)\n",
    "\n",
    "            if _root.left:\n",
    "                flg_l, min_val, max_val, size = isBST(_root.left)\n",
    "                flg = flg and flg_l and (max_val < _root.val)\n",
    "                cur_size += size\n",
    "                cur_min_val = min(cur_min_val, min_val)\n",
    "            \n",
    "            if flg is True:\n",
    "                res = max(res, cur_size)\n",
    "            \n",
    "            return (flg, cur_min_val, cur_max_val, cur_size)\n",
    "        if root:\n",
    "            isBST(root)\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "    \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return float(\"inf\"), float(\"-inf\"), 0\n",
    "            l_min, l_max, lv = dfs(root.left)\n",
    "            r_min, r_max, rv = dfs(root.right)\n",
    "            if l_max < root.val< r_min:\n",
    "                return min(root.val, l_min), max(root.val, r_max), lv + rv + 1\n",
    "            return float(\"-inf\"), float(\"inf\"), max(lv, rv)\n",
    "        return dfs(root)[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.largest_value =1\n",
    "        self.dfs(root)\n",
    "        return self.largest_value\n",
    "    def dfs(self, node):\n",
    "        if not node:\n",
    "            return (False, 0, -10001, 10001)\n",
    "        if not node.left and not node.right:\n",
    "            return (True,1,node.val,node.val)\n",
    "\n",
    "        l_is_bst, l_size,l_min,l_max = self.dfs(node.left)\n",
    "        r_is_bst, r_size,r_min,r_max = self.dfs(node.right)\n",
    "\n",
    "        if l_is_bst and r_is_bst and l_max < node.val<r_min:\n",
    "            cur_size = 1+l_size+r_size\n",
    "            self.largest_value = max(self.largest_value, cur_size)\n",
    "            return (True, cur_size, l_min, r_max)\n",
    "        elif l_is_bst and not node.right and l_max < node.val:\n",
    "            cur_size = 1+l_size\n",
    "            self.largest_value = max(self.largest_value, cur_size)\n",
    "            return (True, cur_size, l_min, node.val)\n",
    "        elif r_is_bst and not node.left and r_min > node.val:\n",
    "            cur_size = 1+r_size\n",
    "            self.largest_value = max(self.largest_value, cur_size)\n",
    "            return (True, cur_size, node.val, r_max)\n",
    "        else:\n",
    "            return (False, 0, -10001, 10001)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return float(\"inf\"), float(\"-inf\"), 0\n",
    "            l_min, l_max, lv = dfs(root.left)\n",
    "            r_min, r_max, rv = dfs(root.right)\n",
    "            if l_max < root.val< r_min:\n",
    "                return min(root.val, l_min), max(root.val, r_max), lv + rv + 1\n",
    "            return float(\"-inf\"), float(\"inf\"), max(lv, rv)\n",
    "        return dfs(root)[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def helper(root,l,r):\n",
    "            if not root:return True\n",
    "            if root.val<=l or root.val>=r:\n",
    "                return False\n",
    "            left=helper(root.left,l,root.val)\n",
    "            right=helper(root.right,root.val,r)\n",
    "            return left and right\n",
    "        def cnt(root):\n",
    "            if root:\n",
    "                return cnt(root.left)+cnt(root.right)+1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        if not root: return 0\n",
    "        if helper(root,float('-inf'),float('inf'))==True:\n",
    "            return cnt(root)\n",
    "        return max(self.largestBSTSubtree(root.left),self.largestBSTSubtree(root.right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        ret = 0\n",
    "        def check_BST(node):\n",
    "            nonlocal ret\n",
    "            if node is None:\n",
    "                return True, None, None, 0\n",
    "            left_flag, left_max, left_min, left_cnt = check_BST(node.left)\n",
    "            right_flag, right_max, right_min, right_cnt = check_BST(node.right)\n",
    "\n",
    "            if not (left_flag and right_flag):\n",
    "                return False, None, None, None\n",
    "            else:\n",
    "                if (not left_max or left_max < node.val) and (not right_min or right_min > node.val):\n",
    "                    left_min = left_min if left_min else node.val\n",
    "                    right_max = right_max if right_max else node.val\n",
    "                    if left_cnt + right_cnt + 1 > ret:\n",
    "                        ret = left_cnt + right_cnt + 1\n",
    "                    return True, right_max, left_min, left_cnt + right_cnt + 1\n",
    "                return False, None, None, None\n",
    "        \n",
    "        check_BST(root)\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=0\n",
    "        if not root:\n",
    "            return 0\n",
    "        def dfs(node):\n",
    "            mark=True\n",
    "            l,h=node.val,node.val\n",
    "            amount=1\n",
    "            if node.left:\n",
    "                ll,lh,lamount,lmark=dfs(node.left)\n",
    "                if not lmark or lh>=l:\n",
    "                    mark=False\n",
    "                l=ll\n",
    "                amount+=lamount\n",
    "            if node.right:\n",
    "                rl,rh,ramount,rmark=dfs(node.right)\n",
    "                if not rmark or rl<=h:\n",
    "                    mark=False\n",
    "                h=rh\n",
    "                amount+=ramount\n",
    "            if mark:\n",
    "                nonlocal ans \n",
    "                ans=max(ans,amount)\n",
    "            #print(l,h,amount,mark)\n",
    "            return l,h,amount,mark\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        ans = []\n",
    "\n",
    "        def cntBST(root): #-> cnt:int, min_n:int, max_n:int\n",
    "            if root is None:\n",
    "                return 0, None, None\n",
    "\n",
    "            if (root.left is None) and (root.right is None):\n",
    "                ans.append(1)\n",
    "                return 1, root.val, root.val\n",
    "            \n",
    "            cnt_l, min_l, max_l = cntBST(root.left)\n",
    "            cnt_r, min_r, max_r = cntBST(root.right)\n",
    "            # print(root.val, cnt_l, min_l, max_l)\n",
    "            # print(root.val, cnt_r, min_r, max_r)\n",
    "            if (cnt_l <0) or (cnt_r<0):\n",
    "                return -1, None, None\n",
    "            \n",
    "            tag = True\n",
    "            if cnt_l>0 and max_l >= root.val:\n",
    "                tag = False\n",
    "            if cnt_r>0 and min_r <= root.val:\n",
    "                tag = False\n",
    "            \n",
    "            if tag:\n",
    "                total = cnt_l+cnt_r+1\n",
    "                ans.append(total)\n",
    "                min_l = min_l if min_l else root.val\n",
    "                max_r = max_r if max_r else root.val\n",
    "                return total, min_l, max_r\n",
    "            else:\n",
    "                return -1, None, None\n",
    "        \n",
    "        cntBST(root)\n",
    "        if ans:\n",
    "            return max(ans)\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ret = 0\n",
    "        def is_bst(node):\n",
    "            if not node:\n",
    "                return 0, 100000, -100000\n",
    "\n",
    "            l_count, lmin, lmax = is_bst(node.left)\n",
    "            r_count, rmin, rmax = is_bst(node.right)\n",
    "            if l_count >= 0 and r_count >= 0 and lmax < node.val < rmin:\n",
    "                count = l_count + r_count + 1\n",
    "                nonlocal ret\n",
    "                ret = max(ret, count)\n",
    "                return count, min(lmin, node.val), max(rmax, node.val)\n",
    "            return -1, 0, 0\n",
    "        is_bst(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def valid(node, l, r):\n",
    "            if not node:\n",
    "                return True\n",
    "            v = node.val\n",
    "            self.count += 1\n",
    "            if v <= l or v >= r:\n",
    "                return False\n",
    "            return valid(node.left, l, v) and valid(node.right, v, r)\n",
    "\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                self.count = 0\n",
    "                if valid(node, -inf, inf):\n",
    "                    self.res = max(self.res, self.count)\n",
    "                    return\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        intmin = float('-inf')\n",
    "        intmax = float('inf')\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return intmax, intmin, 0\n",
    "            count = 1\n",
    "            leftmin, leftmax, leftcnt = dfs(root.left)\n",
    "            rightmin, rightmax, rightcnt = dfs(root.right)\n",
    "            if leftmax < root.val < rightmin:\n",
    "                nonlocal res\n",
    "                res = max(res, leftcnt+rightcnt+1)\n",
    "                return min(root.val, leftmin), max(root.val, rightmax), leftcnt+rightcnt+1\n",
    "            return intmin, intmax, 0\n",
    "        res = 0\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.answer_1(root)\n",
    "\n",
    "    def answer_1(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        if self._is_bst(root):\n",
    "            return self._compute_cnt(root)\n",
    "        return max(self.answer_1(root.left), self.answer_1(root.right))\n",
    "\n",
    "    def _is_bst(self, node, left=float(\"-inf\"), right=float(\"inf\")):\n",
    "        if not node:\n",
    "            return True\n",
    "        if node.val <= left or node.val >= right:\n",
    "            return False\n",
    "        return self._is_bst(node.left, left, node.val) and self._is_bst(node.right, node.val, right)\n",
    "\n",
    "    def _compute_cnt(self, node):\n",
    "        if not node:\n",
    "            return 0\n",
    "        return self._compute_cnt(node.left) + self._compute_cnt(node.right) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def helper(root: Optional[TreeNode]) -> (int, int, int):\n",
    "            if not root: return 0, float('inf'), -float('inf')\n",
    "            left, lmin, lmax = helper(root.left)\n",
    "            right, rmin, rmax = helper(root.right)\n",
    "            if lmax >= root.val or rmin <= root.val:\n",
    "                return max(left, right), -float('inf'), float('inf')\n",
    "            return left + right + 1, min(lmin, root.val), max(rmax, root.val)\n",
    "        return helper(root)[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        maxLen = 0\n",
    "        def getsubTree(root):\n",
    "            # return (bool, len, Maxvalue, Minvalue)\n",
    "            # bool indicate if BST\n",
    "            nonlocal maxLen\n",
    "            if not root:\n",
    "                return (True, 0, float('inf'), float('-inf'))\n",
    "            leftPart = getsubTree(root.left)\n",
    "            rightPart = getsubTree(root.right)\n",
    "            # print(root.val, leftPart,rightPart)\n",
    "            isBST = True\n",
    "            if not leftPart[0]:\n",
    "                isBST = False\n",
    "            elif leftPart[1]>0 and leftPart[2] >= root.val:\n",
    "                isBST = False\n",
    "            if not rightPart[0]:\n",
    "                isBST = False\n",
    "            elif rightPart[1]>0 and rightPart[3] <= root.val:\n",
    "                isBST = False\n",
    "            \n",
    "            if not isBST:\n",
    "                return (False,0,0,0)\n",
    "            maxLen = max(maxLen, leftPart[1]+1+rightPart[1])\n",
    "            # print(root.val, maxLen)\n",
    "            leftmin, rightmin = leftPart[3], rightPart[2]\n",
    "            if leftPart[1] == 0:\n",
    "                leftmin = root.val\n",
    "            if rightPart[1] == 0:\n",
    "                rightmin = root.val\n",
    "            return (True, leftPart[1]+1+rightPart[1], rightmin, leftmin)\n",
    "        getsubTree(root)\n",
    "        return maxLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "\n",
    "        def traverse(node):\n",
    "            if node and not node.left and not node.right:\n",
    "                return node.val, node.val, 1\n",
    "            \n",
    "            minl = float(\"-inf\")\n",
    "            maxl = float(\"-inf\")\n",
    "            cntl = 0\n",
    "            minr = float(\"inf\")\n",
    "            maxr = float(\"inf\")\n",
    "            cntr = 0\n",
    "            \n",
    "            if node.left:\n",
    "                minl, maxl, cntl = traverse(node.left)\n",
    "                \n",
    "            \n",
    "            if node.right:\n",
    "                minr, maxr, cntr = traverse(node.right)\n",
    "            print(minl, maxl, cntl)\n",
    "            print(minr, maxr, cntr)\n",
    "            print(node.val)\n",
    "            \n",
    "            if node.val > maxl and node.val > minl and node.val < minr and node.val < maxr:\n",
    "                self.msize = max(self.msize, cntl + cntr + 1)\n",
    "                return node.val if minl == float(\"-inf\") else minl, node.val if maxr == float(\"inf\") else maxr, cntl + cntr + 1\n",
    "            else:\n",
    "                return float(\"inf\"), float(\"-inf\"), 0\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.msize = 1\n",
    "        traverse(root)\n",
    "        return self.msize\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: TreeNode) -> int:\n",
    "        return self.dfs(root)[2]\n",
    "\n",
    "    def dfs(self, root: TreeNode):\n",
    "        if root == None:\n",
    "            return float('inf'),  float('-inf'),  0   #对所有的父节点。它都是配合的，ok的\n",
    "\n",
    "        L_min, L_max, L_cnt = self.dfs(root.left)\n",
    "        R_min, R_max, R_cnt = self.dfs(root.right)\n",
    "\n",
    "        if L_max < root.val < R_min:                    #若能构成BST\n",
    "            return min(L_min, root.val),  max(root.val, R_max),  L_cnt + R_cnt + 1\n",
    "\n",
    "        else:                                           #不能构成BST\n",
    "            return float('-inf'),  float('inf'),  max(L_cnt, R_cnt) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=0\n",
    "        def dfs(cur):\n",
    "            if cur==None:\n",
    "                return []\n",
    "            nonlocal ans\n",
    "            if cur.left!=None:\n",
    "                l=dfs(cur.left)\n",
    "            else :\n",
    "                l=[True,10000000000,-10000000000,0]\n",
    "            if cur.right!=None:\n",
    "                r=dfs(cur.right)\n",
    "            else :\n",
    "                r=[True,10000000000,-10000000000,0]\n",
    "            if l[0] and r[0] and l[2]<cur.val<r[1]:\n",
    "                ans=max(ans,r[3]+l[3]+1)\n",
    "                return [True,min(l[1],cur.val),max(cur.val,r[2]),r[3]+l[3]+1]\n",
    "            else :\n",
    "                return [False,10000000000,-10000000000,0]\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def check(node):\n",
    "            if node:\n",
    "                self.count += 1\n",
    "                check(node.left)\n",
    "                check(node.right)\n",
    "            return self.count\n",
    "\n",
    "        def valid(node, l, r):\n",
    "            if not node:\n",
    "                return True\n",
    "            v = node.val\n",
    "            if v <= l or v >= r:\n",
    "                return False\n",
    "            return valid(node.left, l, v) and valid(node.right, v, r)\n",
    "\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if valid(node, -inf, inf):\n",
    "                    self.count = 0\n",
    "                    self.res = max(self.res, check(node))\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return float(\"inf\"), -float(\"inf\"), 0\n",
    "            else:\n",
    "                l_min, l_max, l_size = helper(root.left)\n",
    "                r_min, r_max, r_size = helper(root.right)\n",
    "                if l_max < root.val < r_min:\n",
    "                    return min(l_min, root.val), max(r_max, root.val), 1+l_size+r_size\n",
    "                else:\n",
    "                    return float(\"-inf\"), float(\"inf\"), max(l_size, r_size)\n",
    "        \n",
    "        return helper(root)[2]\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def find(root: Optional[TreeNode])->Tuple[List[int],bool]:\n",
    "            nonlocal res\n",
    "            if not root: return [10**5,-10**5,0],True\n",
    "            l,lb = find(root.left)\n",
    "            r,rb = find(root.right)\n",
    "            if not lb or not rb: return [0],False\n",
    "            if l[1]<root.val and r[0]>root.val:\n",
    "                num = l[2]+r[2]+1\n",
    "                res = max(res,num)\n",
    "                min_v = l[0] if root.left else root.val\n",
    "                max_v = r[1] if root.right else root.val\n",
    "                return [min_v,max_v,num],True\n",
    "            else:\n",
    "                return [0],False\n",
    "\n",
    "        find(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=1\n",
    "        \n",
    "        def dfs(r):\n",
    "            if not r:\n",
    "                return float(\"inf \"),-float(\"inf\"),0\n",
    "            lmin,lmax,lcnt=dfs(r.left)\n",
    "            rmin,rmax,rcnt=dfs(r.right)\n",
    "\n",
    "            if lmax<r.val<rmin:\n",
    "                return min(r.val,lmin), max(rmax,r.val),lcnt+rcnt+1\n",
    "            \n",
    "            else:\n",
    "                return float(\"-inf \"),float(\"inf\"),max(lcnt,rcnt)\n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "        return dfs(root)[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(self, root):\n",
    "            if not root:\n",
    "                return float('inf'),  float('-inf'),  0 \n",
    "            \n",
    "            leftMin, leftMax, leftCnt = dfs(self, root.left)\n",
    "            rightMin, rightMax, rightCnt = dfs(self, root.right)\n",
    "            if leftMax < root.val < rightMin:\n",
    "                return min(leftMin, root.val),  max(root.val, rightMax),  leftCnt + rightCnt + 1\n",
    "            else:\n",
    "                return float('-inf'),  float('inf'),  max(leftCnt, rightCnt) \n",
    "        return dfs(self, root)[2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=0\n",
    "        def dfs(cur):\n",
    "            if cur==None:\n",
    "                return []\n",
    "            nonlocal ans\n",
    "            if cur.left!=None:\n",
    "                l=dfs(cur.left)\n",
    "            else :\n",
    "                l=[True,10000000000,-10000000000,0]\n",
    "            if cur.right!=None:\n",
    "                r=dfs(cur.right)\n",
    "            else :\n",
    "                r=[True,10000000000,-10000000000,0]\n",
    "            if l[0] and r[0] and l[2]<cur.val<r[1]:\n",
    "                ans=max(ans,r[3]+l[3]+1)\n",
    "                return [True,min(l[1],cur.val),max(cur.val,r[2]),r[3]+l[3]+1]\n",
    "            else :\n",
    "                return [False,10000000000,-10000000000,0]\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return 1e5, -1e5, 0\n",
    "            \n",
    "            l_min, l_max, l_num = dfs(node.left)\n",
    "            r_min, r_max, r_num = dfs(node.right)\n",
    "\n",
    "            if l_max < node.val < r_min:\n",
    "                return min(l_min, node.val), max(r_max, node.val), l_num + r_num + 1\n",
    "            else:\n",
    "                return -1e5, 1e5, max(l_num, r_num)\n",
    "        return dfs(root)[2]\n",
    "    # def largestBSTSubtree(self, root: TreeNode) -> int:\n",
    "    #     return self.dfs(root)[2]\n",
    "\n",
    "    # def dfs(self, root: TreeNode):\n",
    "    #     if root == None:\n",
    "    #         return float('inf'),  float('-inf'),  0   #对所有的父节点。它都是配合的，ok的\n",
    "\n",
    "    #     L_min, L_max, L_cnt = self.dfs(root.left)\n",
    "    #     R_min, R_max, R_cnt = self.dfs(root.right)\n",
    "\n",
    "    #     if L_max < root.val < R_min:                    #若能构成BST\n",
    "    #         return min(L_min, root.val),  max(root.val, R_max),  L_cnt + R_cnt + 1\n",
    "\n",
    "    #     else:                                           #不能构成BST\n",
    "    #         return float('-inf'),  float('inf'),  max(L_cnt, R_cnt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        count = 0\n",
    "        \n",
    "        Min, Max = float(\"-inf\"), float(\"inf\")\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return Max, Min, 0\n",
    "            lmin, lmax, lcnt = dfs(node.left)\n",
    "            rmin, rmax, rcnt = dfs(node.right)\n",
    "            if lmax < node.val < rmin:\n",
    "                nonlocal count\n",
    "                count = max(count, lcnt + rcnt + 1)\n",
    "                return min(node.val, lmin), max(node.val, rmax), lcnt + rcnt + 1\n",
    "            return Min, Max, 0\n",
    "        \n",
    "        dfs(root)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        ans = 1\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return [inf, -inf, 0, 1]\n",
    "            mi_l, mx_l, num_l, is_bst_l = dfs(node.left)\n",
    "            mi_r, mx_r, num_r, is_bst_r = dfs(node.right)\n",
    "            if not is_bst_l or not is_bst_r:\n",
    "                return [inf, -inf, 0, 0]\n",
    "            if node.val <= mx_l or node.val >= mi_r:\n",
    "                return [inf, -inf, 0, 0]\n",
    "            ans = max(ans, 1 + num_l + num_r)\n",
    "            return [min(mi_l, node.val), max(node.val, mx_r), 1 + num_l + num_r, 1 ]\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(x):\n",
    "            if x is None:\n",
    "                return inf,-inf,0\n",
    "            l_Min,l_Max,lv=dfs(x.left)\n",
    "            r_Min,r_Max,rv=dfs(x.right)\n",
    "            if l_Max<x.val<r_Min:\n",
    "                return min(l_Min,x.val),max(r_Max,x.val),lv+rv+1\n",
    "            return -inf,inf,max(lv,rv)\n",
    "        return dfs(root)[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "\n",
    "        def traverse(node):\n",
    "            if node and not node.left and not node.right:\n",
    "                return node.val, node.val, 1\n",
    "            \n",
    "            minl = float(\"-inf\")\n",
    "            maxl = float(\"-inf\")\n",
    "            cntl = 0\n",
    "            minr = float(\"inf\")\n",
    "            maxr = float(\"inf\")\n",
    "            cntr = 0\n",
    "            \n",
    "            if node.left:\n",
    "                minl, maxl, cntl = traverse(node.left)            \n",
    "            if node.right:\n",
    "                minr, maxr, cntr = traverse(node.right)\n",
    "\n",
    "            \n",
    "            if node.val > maxl and node.val > minl and node.val < minr and node.val < maxr:\n",
    "                self.msize = max(self.msize, cntl + cntr + 1)\n",
    "                return node.val if minl == float(\"-inf\") else minl, node.val if maxr == float(\"inf\") else maxr, cntl + cntr + 1\n",
    "            else:\n",
    "                return float(\"inf\"), float(\"-inf\"), 0\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.msize = 1\n",
    "        traverse(root)\n",
    "        return self.msize\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return inf,-inf,0\n",
    "            lmin,lmax,lnum=dfs(root.left)\n",
    "            rmin,rmax,rnum=dfs(root.right)\n",
    "            if root.val>lmax and root.val<rmin:\n",
    "                nonlocal ans\n",
    "                ans=max(ans,lnum+rnum+1)\n",
    "                return min(lmin,root.val),max(rmax,root.val),lnum+rnum+1\n",
    "            return -inf,inf,0\n",
    "        dfs(root)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    ans = 0\n",
    "\n",
    "    def helper(self, root):\n",
    "        if not root:\n",
    "            return -float('inf'), float('inf'), 0\n",
    "        \n",
    "        left_max, left_min, left_node_num = self.helper(root.left)\n",
    "        right_max, right_min, right_node_num = self.helper(root.right)\n",
    "\n",
    "        max_, min_ = float('inf'), -float('inf') \n",
    "        node_sum = 0\n",
    "        if root.val > left_max and root.val < right_min:\n",
    "            self.ans = max(self.ans, left_node_num + right_node_num + 1)\n",
    "            max_ = max(right_max, root.val)\n",
    "            min_ = min(left_min, root.val)\n",
    "            node_sum = left_node_num + right_node_num + 1\n",
    "        \n",
    "        return max_, min_, node_sum\n",
    "\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.helper(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return True, 0, inf, -inf\n",
    "            isL, numL, leftMin, leftMax = dfs(root.left)\n",
    "            isR, numR, rightMin, rightMax = dfs(root.right)\n",
    "            if(isL and isR and leftMax < root.val < rightMin):\n",
    "                res = max(res, numL + numR + 1)\n",
    "                return True, numL + numR + 1, min(root.val, leftMin), max(root.val, rightMax)\n",
    "            return False, 0, 0, 0\n",
    "        dfs(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node) -> (bool, int, int, int):\n",
    "            nonlocal ans\n",
    "\n",
    "            lflag, lmin, lmax, llen = True, node.val, node.val, 0\n",
    "            rflag, rmin, rmax, rlen = True, node.val, node.val, 0\n",
    "\n",
    "            if node.left is not None:\n",
    "                lflag, lmin, lmax, llen = dfs(node.left)\n",
    "            if node.right is not None:\n",
    "                rflag, rmin, rmax, rlen = dfs(node.right)\n",
    "\n",
    "            if lflag and rflag and (llen == 0 or lmax < node.val) and (rlen == 0 or node.val < rmin):\n",
    "                ans = max(ans, llen + 1 + rlen)\n",
    "                return (True, lmin, rmax, llen + 1 + rlen)\n",
    "            else:\n",
    "                return (False, None, None, None)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        if root is not None:\n",
    "            dfs(root)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ret = 0\n",
    "        def is_bst(node):\n",
    "            if not node:\n",
    "                return 0, 100000, -100000\n",
    "\n",
    "            l_count, lmin, lmax = is_bst(node.left)\n",
    "            r_count, rmin, rmax = is_bst(node.right)\n",
    "            if l_count >= 0 and r_count >= 0 and lmax < node.val < rmin:\n",
    "                count = l_count + r_count + 1\n",
    "                nonlocal ret\n",
    "                ret = max(ret, count)\n",
    "                return count, min(lmin, node.val), max(rmax, node.val)\n",
    "            return -1, 0, 0\n",
    "        is_bst(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=0\n",
    "        def dfs(cur):\n",
    "            if cur==None:\n",
    "                return []\n",
    "            nonlocal ans\n",
    "            if cur.left!=None:\n",
    "                l=dfs(cur.left)\n",
    "            else :\n",
    "                l=[True,10000000000,-10000000000,0]\n",
    "            if cur.right!=None:\n",
    "                r=dfs(cur.right)\n",
    "            else :\n",
    "                r=[True,10000000000,-10000000000,0]\n",
    "            if l[0] and r[0] and l[2]<cur.val<r[1]:\n",
    "                ans=max(ans,r[3]+l[3]+1)\n",
    "                return [True,min(l[1],cur.val),max(cur.val,r[2]),r[3]+l[3]+1]\n",
    "            else :\n",
    "                return [False,10000000000,-10000000000,0]\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.result = 0\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return True, 0, float('inf'), float('-inf')\n",
    "            \n",
    "            is_left_bst, left_size, left_min, left_max = dfs(node.left)\n",
    "            is_right_bst, right_size, right_min, right_max = dfs(node.right)\n",
    "            # 如果左右子树都是BST，并且左子树的最大值小于当前节点的值，右子树的最小值大于当前节点的值，那么当前子树也是BST\n",
    "            if is_left_bst and is_right_bst and left_max < node.val < right_min:\n",
    "                size = left_size + right_size + 1     # 计算当前子树的节点数量，包括当前节点在内 \n",
    "                self.result = max(self.result, size)  # 记录最大BST子树节点数量\n",
    "                return True, size, min(left_min, node.val), max(right_max, node.val)\n",
    "            \n",
    "            return False, 0, 0, 0\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        max_b_tree_cnt = [0]\n",
    "\n",
    "        def traverse(node): # return max, min, BST count\n",
    "            if not node: \n",
    "                return -float('inf'), float('inf'), 0\n",
    "            left_max, left_min, left_cnt = traverse(node.left)\n",
    "            right_max, right_min, right_cnt = traverse(node.right)\n",
    "            if left_max < node.val < right_min: \n",
    "                cur_cnt = left_cnt + right_cnt + 1\n",
    "                max_b_tree_cnt[0] = max(cur_cnt, max_b_tree_cnt[0])\n",
    "                return max(left_max, node.val, right_max), min(left_min, node.val, right_min), cur_cnt\n",
    "            else: \n",
    "                return max(left_max, node.val, right_max), min(left_min, node.val, right_min), -float('inf')\n",
    "        \n",
    "        _, _, a = traverse(root)\n",
    "        return max_b_tree_cnt[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        # max,min,isBST\n",
    "        def process1(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            else:\n",
    "                leftInfo=process1(node.left)\n",
    "                rightInfo=process1(node.right)\n",
    "\n",
    "                maxValue=node.val\n",
    "                if leftInfo:\n",
    "                    maxValue=max(maxValue,leftInfo[0])\n",
    "                if rightInfo:\n",
    "                    maxValue=max(maxValue,rightInfo[0])\n",
    "                \n",
    "                minValue=node.val\n",
    "                if leftInfo:\n",
    "                    minValue=min(minValue,leftInfo[1])\n",
    "                if rightInfo:\n",
    "                    minValue=min(minValue,rightInfo[1])\n",
    "\n",
    "                isBST=True\n",
    "                if leftInfo and leftInfo[2]==False:\n",
    "                    isBST=False\n",
    "                if rightInfo and rightInfo[2]==False:\n",
    "                    isBST=False\n",
    "                if leftInfo and leftInfo[0]>=node.val:\n",
    "                    isBST=False\n",
    "                if rightInfo and rightInfo[1]<=node.val:\n",
    "                    isBST=False\n",
    "                \n",
    "                maxSize=1\n",
    "                if isBST:\n",
    "                    if leftInfo:\n",
    "                        maxSize+=leftInfo[3]\n",
    "                    if rightInfo:\n",
    "                        maxSize+=rightInfo[3]\n",
    "                else:\n",
    "                    if leftInfo:\n",
    "                            maxSize=max(maxSize,leftInfo[3])\n",
    "                    if rightInfo:\n",
    "                            maxSize=max(maxSize,rightInfo[3])\n",
    "                        \n",
    "                return maxValue,minValue,isBST,maxSize\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        return process1(root)[3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "\n",
    "        def dfs(node: Optional[TreeNode]) -> (bool, int, int, int):\n",
    "            if not node:\n",
    "                return (True, 0, -inf, inf)\n",
    "            l_res, l_cnt, l_mx, l_mn = dfs(node.left)\n",
    "            r_res, r_cnt, r_mx, r_mn = dfs(node.right)\n",
    "\n",
    "            if l_res and r_res and l_mx < node.val and r_mn > node.val:\n",
    "                res = l_cnt + r_cnt + 1\n",
    "                self.ans = max(self.ans, res)\n",
    "                return (True, res, max(r_mx, node.val), min(l_mn, node.val))\n",
    "            return (False, 0, 0, 0)\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: TreeNode) -> int:\n",
    "        #无脑dfs\n",
    "        if root == None:\n",
    "            return 0\n",
    "        if self.isBST(root, -0x3f3f3f3f, 0x3f3f3f3f) == True:\n",
    "            return self.cnt(root)\n",
    "        return max(self.largestBSTSubtree(root.left), self.largestBSTSubtree(root.right))\n",
    "\n",
    "    def isBST(self, root: TreeNode, L: int, R: int) -> bool:    #判断一棵树是否为BST\n",
    "        if root == None:\n",
    "            return True\n",
    "        if root.val <= L or R <= root.val:\n",
    "            return False\n",
    "        return self.isBST(root.left, L, root.val) and self.isBST(root.right, root.val, R)\n",
    "\n",
    "    def cnt(self, root: TreeNode) -> int:       #统计树的结点个数\n",
    "        if root == None:\n",
    "            return 0\n",
    "        return self.cnt(root.left) + self.cnt(root.right) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "\n",
    "        def traverse(node):\n",
    "            if node and not node.left and not node.right:\n",
    "                return True, node.val, node.val, 1\n",
    "            \n",
    "            minl = maxl = float(\"-inf\")\n",
    "            cntl = cntr = 0\n",
    "            minr = maxr = float(\"inf\")\n",
    "            flag = True\n",
    "            \n",
    "            if node.left:\n",
    "                f1, minl, maxl, cntl = traverse(node.left)  \n",
    "                flag = f1 and flag          \n",
    "            if node.right:\n",
    "                f2, minr, maxr, cntr = traverse(node.right)\n",
    "                flag = f2 and flag    \n",
    "\n",
    "            if flag and node.val > maxl and node.val < minr:\n",
    "                self.msize = max(self.msize, cntl + cntr + 1)\n",
    "                mi = node.val if minl == float(\"-inf\") else minl\n",
    "                ma = node.val if maxr == float(\"inf\") else maxr\n",
    "                return True, mi, ma, cntl + cntr + 1\n",
    "            else:\n",
    "                return False, 0, 0, 0\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.msize = 1\n",
    "        traverse(root)\n",
    "        return self.msize\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "\n",
    "        _min, _max = float('-inf'), float('inf')\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return _max, _min, 0\n",
    "            lmin, lmax, lcnt = dfs(root.left)\n",
    "            rmin, rmax, rcnt = dfs(root.right)\n",
    "            if lmax < root.val and root.val < rmin:\n",
    "                self.ans = max(self.ans, lcnt + rcnt + 1)\n",
    "                return min(root.val, lmin), max(root.val, rmax), lcnt + rcnt + 1\n",
    "            return _min, _max, 0\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, node):\n",
    "        if not node:\n",
    "            return float('inf'), float('-inf'), 0\n",
    "        lmin, lmax, lcnt = self.dfs(node.left)\n",
    "        rmin, rmax, rcnt = self.dfs(node.right)\n",
    "        if lmax < node.val < rmin:\n",
    "            self.ans = max(self.ans, lcnt+ rcnt + 1)\n",
    "            return min(node.val,lmin),max(node.val,rmax), lcnt + rcnt + 1\n",
    "        return float('-inf'), float('inf'), 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return True, 0, inf, -inf\n",
    "            isL, numL, leftMin, leftMax = dfs(root.left)\n",
    "            isR, numR, rightMin, rightMax = dfs(root.right)\n",
    "            # print(leftMin, leftMax, rightMin, rightMax)\n",
    "            if(isL and isR and leftMax < root.val < rightMin):\n",
    "                res = max(res, numL + numR + 1)\n",
    "                # maxVal = rightMax if rightMax != -inf else root.val\n",
    "                # minVal = leftMin if leftMin != inf else root.val\n",
    "                return True, numL + numR + 1, min(root.val, leftMin), max(root.val, rightMax)\n",
    "            return False, 0, 0, 0\n",
    "        dfs(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        ret_cnt = 0\n",
    "\n",
    "        def check_BST_tree(node):\n",
    "            nonlocal ret_cnt\n",
    "            if not node:\n",
    "                return True, 0, None, None\n",
    "            \n",
    "            left_flag, left_cnt, left_min, left_max = check_BST_tree(node.left)\n",
    "            right_flag, right_cnt, right_min, right_max = check_BST_tree(node.right)\n",
    "\n",
    "            if not left_flag or not right_flag:\n",
    "                return False, None, None, None\n",
    "            \n",
    "            if (not left_max or node.val > left_max) and (not right_min or node.val < right_min):\n",
    "                min_val = left_min if left_min else node.val\n",
    "                max_val = right_max if right_max else node.val\n",
    "                cnt = 1 + left_cnt + right_cnt\n",
    "                if cnt > ret_cnt:\n",
    "                    ret_cnt = cnt\n",
    "                return True, cnt, min_val, max_val\n",
    "            else:\n",
    "                return False, None, None, None\n",
    "        \n",
    "        check_BST_tree(root)\n",
    "        return ret_cnt\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(h):\n",
    "            nonlocal ans\n",
    "            hmax = h.val\n",
    "            hmin = h.val\n",
    "            hsize = 1\n",
    "            f = True\n",
    "\n",
    "            if h.left is not None:\n",
    "                lmax, lmin, lsize, lf = dfs(h.left)\n",
    "                hmax = max(hmax, lmax)\n",
    "                hmin = min(hmin, lmin)\n",
    "                hsize += lsize\n",
    "                if not lf or h.val <= lmax:\n",
    "                    f = False\n",
    "            \n",
    "            if h.right is not None:\n",
    "                rmax, rmin, rsize, rf = dfs(h.right)\n",
    "                hmax = max(hmax, rmax)\n",
    "                hmin = min(hmin, rmin)\n",
    "                hsize += rsize\n",
    "                if not rf or h.val >= rmin:\n",
    "                    f = False\n",
    "            if f:\n",
    "                ans = max(ans, hsize)\n",
    "                print(h.val)\n",
    "            \n",
    "            return (hmax, hmin, hsize, f)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        m = 1\n",
    "        def dfs(root):\n",
    "            nonlocal m\n",
    "            if not root:\n",
    "                return 0,10001,-10001\n",
    "            if (not root.left) and (not root.right):\n",
    "                return 1,root.val,root.val\n",
    "            l,lmi,lma = dfs(root.left)\n",
    "            r,rmi,rma = dfs(root.right)\n",
    "            if l==-1 or r==-1:\n",
    "                return -1,10001,-10001\n",
    "            if l==0 and r==0:\n",
    "                cur = 1\n",
    "            elif l==0:\n",
    "                if r==-1 or root.val>=rmi:\n",
    "                    cur = -1\n",
    "                else:\n",
    "                    cur = r+1\n",
    "            elif r==0:\n",
    "                if l==-1 or root.val<=lma:\n",
    "                    cur = -1\n",
    "                else:\n",
    "                    cur = l+1\n",
    "            else:\n",
    "                if l==-1 or r==-1:\n",
    "                    cur = -1\n",
    "                elif lma<root.val<rmi:\n",
    "                    cur = l+r+1\n",
    "                else:\n",
    "                    cur = -1\n",
    "            m = max(cur,m)\n",
    "            return cur,min(root.val,lmi),max(root.val,rma)\n",
    "        _ = dfs(root)\n",
    "        return m"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
